Natively we just follow the algorithm, since banning the next senate gives up the best advantage, we do that.
class Solution {
public String predictPartyVictory(String senate) {
// baning the new opposite party be the best
StringBuilder senates = new StringBuilder(senate); // for easy deletion
// Count of Each Type of Senator to check for Winner
int rCount = 0;
int dCount = 0;
for (int i = 0; i < senates.length(); i++) {
if (senates.charAt(i) == 'R') {
rCount++;
} else {
dCount++;
}
}
int turn = 0;
while(rCount > 0 && dCount > 0){
// we have power still
if(senates.charAt(turn) == 'R'){
// we going to ban next D
boolean banning_from_before = ban(senates,'D',(turn + 1) % senates.length());
if(banning_from_before){
turn --; //there is one opponent banned before this index, next to go is just next in turn
}
dCount --;
}else{
boolean banning_from_before = ban(senates,'R',(turn + 1) % senates.length());
if(banning_from_before){
turn --; //there is one opponent banned before this index, next to go is just next in turn
}
rCount --;
}
turn = (turn + 1) % senates.length();
}
if(rCount == 0){
return "Dire";
}else{
return "Radiant";
}
}
private boolean ban(StringBuilder sb, Character party, int start){
boolean flag = false;
for(int i = start; i < start + sb.length(); i ++){
int curr = i % sb.length();
if(curr == 0) flag = true;
if(sb.charAt(curr) == party){
sb.deleteCharAt(curr);
break;
}
}
return flag;
}
}
A better solution for this is using some datasturcture to impvore our time complecity. Which structure serves first in first out? that is right a queue
class Solution {
public String predictPartyVictory(String senate) {
// we still know the running curr senate for each party
int rCount = 0, dCount = 0;
// Floating Ban Count
int dFloatingBan = 0, rFloatingBan = 0;
// Queue of senators
Queue<Character> q = new LinkedList<>();
for(char c : senate.toCharArray()){
q.add(c);
if(c == 'R') rCount ++;
else dCount ++;
}
while(rCount > 0 && dCount > 0){
char curr = q.poll();
if(curr == 'D') {
if(dFloatingBan > 0){
// we are banning this guy
dFloatingBan --;
dCount --;
}else{
rFloatingBan ++; // banning next R
q.add('D'); // adds back
}
}else{
// same thing for ther other party
if(rFloatingBan > 0){
rFloatingBan --;
rCount --;
}else{
dFloatingBan ++;
q.add('R');
}
}
}
return rCount == 0 ? "Dire" : "Radiant";
}
}